package com.company.dp;

/**
 * @author jrue
 * @description https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
 * @date 2019/11/18 15:53
 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
 *
 * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
 *
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 *
 * 输入: [7,1,5,3,6,4]
 * 输出: 7
 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
 *      随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
 *
 */
public class MaxProfit {

    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7}));
    }

    // leetcode 解法 原理很简单 但是是怎么想的
    public int maxProfit02(int[] prices) {
        int ans=0;
        for(int i=1;i<=prices.length-1;i++)
        {
            if(prices[i]>prices[i-1])
            {
                ans+=prices[i]-prices[i-1];
            }
        }
        return ans;
    }

    // 我的解法
    public static int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        boolean[] buy = new boolean[prices.length];
        int[] dp = new int[prices.length];

        dp[0] = 0;

        for (int i = 1; i < prices.length; i++) {
            dp[i] = dp[i - 1];
            int buyi = 0;
            int buyj = 0;
            boolean flag = false;
            for (int j = i - 1; j >= 0; j --) {
                if (buy[j]) {
                    if (prices[i] > prices[j]) {
                        if (dp[i] > dp[j] + (prices[i] - prices[j])) break;
                        dp[i] = dp[j] + (prices[i] - prices[j]);
                        buy[i] = true;
                        buy[j] = false;
                    }
                    break;
                }else {
                    if (prices[i] - prices[j] + dp[i - 1] > dp[i]) {
                        dp[i] = prices[i] - prices[j] + dp[i - 1];
                        flag = true;
                        buyi = i;
                        buyj = j;
                    }
                }
            }
            if (flag) {
                buy[buyi] = true;
                buy[buyj] = true;
            }
        }

        System.out.println();
        return dp[prices.length - 1];
    }

}
